// 考虑数字的二进制形式，对于出现三次的数字，各二进制出现的次数都是 3 的倍数
// 因此，统计所有数字的各二进制中 1 的出现次数，并对 3 求余，结果则为出现一次的数字

// 有限状态自动机
// 异或运算：x ^ 0 = x   x ^ 1 = ~x
// 与运算：x & 0 = 0   x & 1 = x

var singleNumber = function (nums) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    // 确定每一位
    let sum = 0;
    for (let j = 0; j < nums.length; j++) {
      // 统计当前位置有多少个元素
      sum += (nums[j] >> i) & 1;
    }
    // 还原到第 i 个位置
    res ^= (sum % 3) << i;
  }
  return res;
}